package org.campuscontent.model;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;

public class AbstractGraph 
{
	ArrayList<AbstractEdge> edgeList;
	ArrayList<AbstractNode> nodeList;
	
	Integer	nodeCnt;
	
	public AbstractGraph()
	{
		edgeList	= new ArrayList<AbstractEdge>();
		nodeList	= new ArrayList<AbstractNode>();
		
		nodeCnt		= 0;
	}
	
	public String addNode(int type)
	{
		nodeCnt++;
		
		nodeList.add(new AbstractNode("Cell"+nodeCnt.toString(), type));
		
		return "Cell"+nodeCnt.toString();
	}
	
	public void addEdge(String label, AbstractNode sNode, AbstractNode eNode)
	{
		edgeList.add(new AbstractEdge(label, sNode, eNode));
	}
	
	public AbstractNode getNodeByLabel(String label)
	{
		for(int i=0; i<nodeList.size(); i++)
		{
			AbstractNode currentNode = nodeList.get(i);
			if(currentNode.getLabel().equals(label))
				return currentNode;
		}
		
		return null;
	}
	
	public int getNodeCnt()
	{
		return nodeList.size();
	}
	
	public String getNodeLabel(int i)
	{
		return nodeList.get(i).getLabel();
	}
	
	public int getNodeType(int i)
	{
		return nodeList.get(i).getType();
	}
	
	public AbstractNode getNode(int i)
	{
		return nodeList.get(i);
	}
	
	public int getEdgeCnt()
	{
		return edgeList.size();
	}
	
	public String getEdgeLabel(int i)
	{
		return edgeList.get(i).getLabel();
	}
	
	public String getsNode(int i)
	{
		return edgeList.get(i).getsNode().getLabel();
	}
	
	public String geteNode(int i)
	{
		return edgeList.get(i).geteNode().getLabel();
	}
	
	public AbstractEdge getEdge(int i)
	{
		return edgeList.get(i);
	}
	
	
	
	
	
	public AbstractGraph addLoop()
	{		
		AbstractNode oldSNode, oldENode;
		AbstractNode newSNode, newENode;
		
		oldSNode	=	getStartNode();
		oldENode	= 	getEndNode();
		
		oldSNode.setType(0);
		oldENode.setType(0);
		
		newSNode	= getNodeByLabel(addNode(1));
		newENode	= getNodeByLabel(addNode(2));
		
		addEdge("empty",	newSNode,	oldSNode);
		addEdge("empty",	newSNode,	oldENode);
		addEdge("empty",	oldENode,	oldSNode);
		addEdge("empty",	oldENode, 	newENode);
		
		return this;
	}
	
	public AbstractGraph combineGraph(AbstractGraph nGraph)
	{
		
		String nodeLabel;
		
		HashMap<String, String>		labelTable	= new HashMap<String, String>();
		int 	nodeType;
		
		AbstractNode 	oldSNode, oldENode;
		String			edgeLabel, edgeSNode, edgeENode;
		
		
		
		
		//append all nodes in the new graph and construct the mapping table
		for(int i=0; i<nGraph.getNodeCnt(); i++)
		{
			nodeType	= nGraph.getNodeType(i);
			nodeLabel	= nGraph.getNodeLabel(i);
			labelTable.put(nodeLabel, addNode(nodeType));
			
			//if the appended node is start node
			if(nodeType==1)
			{
				oldENode	= getEndNode();
				oldENode.setType(0);
				
				oldSNode	= getNodeByLabel((String)labelTable.get(nodeLabel));
				oldSNode.setType(0);
				
				addEdge("empty", oldENode, oldSNode);
			}
		}
		
		//append all edges in the new graph
		for(int i=0; i<nGraph.getEdgeCnt(); i++)
		{
			edgeLabel	= nGraph.getEdgeLabel(i);
			edgeSNode	= nGraph.getsNode(i);
			edgeENode	= nGraph.geteNode(i);
			
			addEdge(edgeLabel, getNodeByLabel((String)labelTable.get(edgeSNode)), getNodeByLabel((String)labelTable.get(edgeENode)));
		}
		
		return this;
	}
	
	public AbstractGraph minimize()
	{
		boolean minimizable	= true;
		
		AbstractNode sourceNode, targetNode;
		
		while(minimizable)
		{
			minimizable	= false;
			for(int i = 0; i < getNodeCnt() ; i++)
				for(int j = 0; j < getNodeCnt(); j++)
			{
				if(i==j)
					continue;
				
				sourceNode	= nodeList.get(i);
				targetNode	= nodeList.get(j);
				
				if((sourceNode.getType()==targetNode.getType() || sourceNode.getType()+targetNode.getType()==5 || sourceNode.getType()+targetNode.getType()==1)
						&& hasSameOutConnection(sourceNode, targetNode))
				{
					joinNode(sourceNode, targetNode);
					minimizable	= true;
					break;
				}
				
			}
		}
		
		
		return this;
	}
	
	void joinNode(AbstractNode sourceNode, AbstractNode targetNode)
	{
		AbstractNode tempNode;
		
		
		//determine which node will be combined
		if(targetNode.getType()==3)
		{
			tempNode 	= 	sourceNode;
			sourceNode	=	targetNode;
			targetNode	=	tempNode;			
		}
		else if(targetNode.getType()==0)
		{
			sourceNode.setType(0);
		}
	
		
		//transfer all the in connections of the target node to source node
		ArrayList<AbstractEdge> inConnection = getInConnection(targetNode);
		
		for(int i = 0; i < inConnection.size(); i++)
		{
			edgeList.add(new AbstractEdge(inConnection.get(i).getLabel(), inConnection.get(i).getsNode(), sourceNode));
		}
		
		//delete the target node and all connected edge;
		
		removeNode(targetNode);	
	}
	
	void removeNode(AbstractNode node)
	{
		boolean hasMoreConnection = true;
		
		for(int i = 0; i < getNodeCnt(); i++)
		{
			if(nodeList.get(i).getLabel()==node.getLabel())
			{
				nodeList.remove(i);
				break;
			}
		}
		
		while(hasMoreConnection)
		{
			hasMoreConnection = false;
			for(int i = 0; i < getEdgeCnt(); i++)
			{
				if(edgeList.get(i).getsNode().getLabel().equals(node.getLabel())||edgeList.get(i).geteNode().getLabel().equals(node.getLabel()))
				{
					edgeList.remove(i);
					hasMoreConnection = true;
				}
			}
		}
	}
	
	
	
	boolean hasSameOutConnection(AbstractNode sourceNode, AbstractNode targetNode)
	{
		ArrayList<AbstractEdge> sourceOutConnection = getOutConnection(sourceNode);
		ArrayList<AbstractEdge> targetOutConnection = getOutConnection(targetNode);
		
		int edgeIndex;
		
		if(sourceOutConnection.size()!=targetOutConnection.size())
			return false;
		else
		{
			for(int i = 0; i < sourceOutConnection.size(); i++)
			{
				edgeIndex = findEdge(sourceOutConnection.get(i), targetOutConnection);
				
				if(edgeIndex!=-1)
					targetOutConnection.remove(edgeIndex);
			}
			
			if(targetOutConnection.size()!=0)
				return false;
		}
		return true;
	}
	
	int findEdge(AbstractEdge targetEdge, ArrayList<AbstractEdge> edgeList)
	{
		AbstractEdge currentEdge;
		for(int i = 0; i < edgeList.size(); i++)
		{
			currentEdge = edgeList.get(i);
			
			if(currentEdge.geteNode().getLabel().equals(targetEdge.geteNode().getLabel())
					&& currentEdge.getLabel().equals(targetEdge.getLabel()))
				return i;
		}
		return -1;
	}
	
	ArrayList<AbstractEdge> getOutConnection(AbstractNode sourceNode)
	{
		ArrayList<AbstractEdge> outConnection = new ArrayList<AbstractEdge>();
		
		for(int i = 0; i < getEdgeCnt(); i++){
			if(edgeList.get(i).getsNode().getLabel().equals(sourceNode.getLabel()))
				outConnection.add(edgeList.get(i));
		}
		
		return outConnection;
	}
	
	ArrayList<AbstractEdge> getInConnection(AbstractNode targetNode)
	{
		ArrayList<AbstractEdge> inConnection = new ArrayList<AbstractEdge>();
		
		for(int i = 0; i < getEdgeCnt(); i++){
			if(edgeList.get(i).geteNode().getLabel().equals(targetNode.getLabel()))
				inConnection.add(edgeList.get(i));
		}
		
		return inConnection;
	}
	
	public AbstractGraph joinGraph(AbstractGraph nGraph)
	{
		String nodeLabel;
		
		AbstractNode oldSNode, oldENode;
		AbstractNode newSNode, newENode;
		
		HashMap<String, String>		labelTable	= new HashMap<String, String>();
		int 	nodeType;
		
		
		String			edgeLabel, edgeSNode, edgeENode;
		
		oldSNode	=	getStartNode();
		oldENode	= 	getEndNode();
		
		oldSNode.setType(0);
		oldENode.setType(0);
		
		
		
		newSNode	= getNodeByLabel(addNode(1));
		newENode	= getNodeByLabel(addNode(2));
		
		addEdge("empty",	newSNode,	oldSNode);
		addEdge("empty",	oldENode, newENode);
		
		
		//append all nodes in the new graph and construct the mapping table
		for(int i=0; i<nGraph.getNodeCnt(); i++)
		{
			nodeType	= nGraph.getNodeType(i);
			nodeLabel	= nGraph.getNodeLabel(i);
			labelTable.put(nodeLabel, addNode(nodeType));
			
			//if the appended node is start node
			if(nodeType==1)
			{
				newSNode	= getStartNode();
				
				
				oldSNode	= getNodeByLabel((String)labelTable.get(nodeLabel));
				oldSNode.setType(0);
				
				addEdge("empty", newSNode, oldSNode);
			}
			
			//if the appended node is end node
			//if the appended node is start node
			if(nodeType==2)
			{
				newENode	= getEndNode();
							
				oldENode	= getNodeByLabel((String)labelTable.get(nodeLabel));
				oldENode.setType(0);
				
				addEdge("empty", oldENode, newENode);
			}
		}
		
		//append all edges in the new graph
		for(int i=0; i<nGraph.getEdgeCnt(); i++)
		{
			edgeLabel	= nGraph.getEdgeLabel(i);
			edgeSNode	= nGraph.getsNode(i);
			edgeENode	= nGraph.geteNode(i);
			
			addEdge(edgeLabel, getNodeByLabel((String)labelTable.get(edgeSNode)), getNodeByLabel((String)labelTable.get(edgeENode)));
		}
		
		//create the new start and end node with corresponding connections
		
		
		return this;
	}
	
	public AbstractGraph eliminateEmpty()
	{
		String nodeLabel;
		

		
		AbstractNode oldSNode, oldENode;
		AbstractNode newSNode, newENode;
	
		ArrayList<AbstractNode> currentENode	= new ArrayList<AbstractNode>();
		
		HashMap<String, String>		labelTable	= new HashMap<String, String>();
		HashMap<String, String>		revLabelTable	= new HashMap<String, String>();
		int 	nodeType;
		
	
		
		AbstractGraph	newGraph	= new AbstractGraph();
		
		//append virtual empty edge
		boolean hasVirtual = true;
		
		while(hasVirtual)
		{
			hasVirtual	= false;
			for(int i = 0; i < getNodeCnt(); i++)
				for(int j = 0; j < getNodeCnt(); j++)
				{
					for(int k = 0; k < getNodeCnt(); k++)
					{
						newSNode	= getNode(i);
						newENode	= getNode(j);
						
						
						
						if((getEdgeByNode(newSNode, getNode(k))!=null && getEdgeByNode(newSNode, getNode(k)).getLabel().equals("empty")) &&
								(getEdgeByNode(getNode(k), newENode)!=null && getEdgeByNode(getNode(k), newENode).getLabel().equals("empty")) &&
								getEdgeByNode(newSNode, newENode)==null)
						{
							addEdge("empty", newSNode, newENode);
							hasVirtual = true;
						}
					}
				}
		}
		
		
		//append all nodes to the new graph and construct the mapping table
		for(int i=0; i<getNodeCnt(); i++)
		{
			nodeType	= getNodeType(i);
			nodeLabel	= getNodeLabel(i);
			
			//if the appended node is start node
			if(nodeType==1)
			{
				labelTable.put(nodeLabel, newGraph.addNode(nodeType));			
			}
			else
			{
				//see whether the node has an non-empty entering transition 
				if(hasValidTransition(nodeLabel))
				{
					labelTable.put(nodeLabel, newGraph.addNode(nodeType));		
				}
			}
			
			
		}
		
		//construct reverse label table
		Iterator<String> iterator = labelTable.keySet().iterator();
		while( iterator. hasNext() ){
			String key	= (String)iterator.next();
			revLabelTable.put(labelTable.get(key),key);

		}
		
	
		//for(int i = 0; i < keySet.length; i++)
		{
			//revLabelTable.put(labelTable.get(keySet[i]), keySet[i]);
		}
		
		//determine the new end nodes
		oldENode	= getEndNode();
		
		currentENode.add(oldENode);
		
		for(int i = 0; i < currentENode.size(); i++)
		{
			oldENode	= currentENode.get(i);
			for(int j = 0; j < getEdgeCnt(); j++)
			{
				if(getEdge(j).label.equals("empty") && getEdge(j).geteNode().getLabel().equals(oldENode.getLabel()))
				{
					if(!currentENode.contains(getEdge(j).getsNode()))
						currentENode.add(getEdge(j).getsNode());
				}
					
						
			}			
		}
		
		//set the new end nodes
		for(int i = 0; i < currentENode.size(); i++)
		{
		
			//see if the new end nods are in the new graph;
			if(labelTable.containsKey(currentENode.get(i).getLabel()))
			{
				if(newGraph.getNodeByLabel(labelTable.get(currentENode.get(i).getLabel())).getType()==1)
					newGraph.getNodeByLabel(labelTable.get(currentENode.get(i).getLabel())).setType(3);
				else
					newGraph.getNodeByLabel(labelTable.get(currentENode.get(i).getLabel())).setType(2);
			}
		}
		
		//add the non empty edge to new graph
		for(int i = 0; i < getEdgeCnt(); i++)
		{
			if(!getEdge(i).getLabel().equals("empty"))
			{
				//see if both of the two nodes of a given edge are in the new graph
				if(labelTable.containsKey(getEdge(i).geteNode().getLabel())&& labelTable.containsKey(getEdge(i).getsNode().getLabel()))
				{
					newGraph.addEdge(getEdge(i).getLabel(),
							newGraph.getNodeByLabel(labelTable.get(getEdge(i).getsNode().getLabel())), 
							newGraph.getNodeByLabel(labelTable.get(getEdge(i).geteNode().getLabel())));
				}
			}
		}
		
		//add the bridge edge to the new graph
		for(int i = 0; i < newGraph.getNodeCnt(); i++)
			for(int j = 0; j < newGraph.getNodeCnt(); j++)
			{
				for(int k = 0; k < getNodeCnt(); k++)
				{
					newSNode	= newGraph.getNode(i);
					newENode	= newGraph.getNode(j);
					
					oldSNode	= this.getNodeByLabel(revLabelTable.get(newSNode.getLabel()));
					oldENode	= this.getNodeByLabel(revLabelTable.get(newENode.getLabel()));
					
					if((getEdgeByNode(oldSNode, getNode(k))!=null && getEdgeByNode(oldSNode, getNode(k)).getLabel().equals("empty")) &&
							(getEdgeByNode(getNode(k), oldENode)!=null && !getEdgeByNode(getNode(k), oldENode).getLabel().equals("empty")))
					{
						newGraph.addEdge(getEdgeByNode(getNode(k), oldENode).getLabel(), newSNode, newENode);
					}
				}
			}
		
		
		return newGraph;
	}
	
	public AbstractEdge getEdgeByNode(AbstractNode sNode, AbstractNode eNode)
	{
				
		for(int i = 0; i < getEdgeCnt(); i++)
		{
			if(getEdge(i).getsNode().getLabel().equals(sNode.getLabel())&&
					getEdge(i).geteNode().getLabel().equals(eNode.getLabel()))
					return getEdge(i);
		}
		
		return null;
	}
	
	public boolean hasValidTransition(String nodeLabel)
	{
		AbstractEdge cEdge;
		
		for(int i = 0; i < getEdgeCnt(); i++)
		{
			cEdge	= getEdge(i);
			
			if(!cEdge.getLabel().equals("empty")&&cEdge.geteNode().getLabel().equals(nodeLabel))
				return true;
		}
		return false;
	}
	
	
	public AbstractNode getStartNode()
	{
		for(int i = 0; i < nodeList.size(); i++)
		{
			if(nodeList.get(i).getType()==1)
				return nodeList.get(i);
		}
		
		return null;
	}
	
	public AbstractNode getEndNode()
	{
		for(int i = 0; i < nodeList.size(); i++)
		{
			if(nodeList.get(i).getType()==2)
				return nodeList.get(i);
		}
		
		return null;
	}
	
}

class AbstractNode
{
	String 	label;
	int 	type;
	
	public AbstractNode(String label, int type)
	{
		this.label	= label;
		this.type	= type;
	}
	
	public String getLabel()
	{
		return label;
	}
	
	public int getType()
	{
		return type;
	}
	
	public void setType(int type)
	{
		this.type	= type;
	}
}

class AbstractEdge
{
	AbstractNode 	sNode, eNode;
	String			label;	
	
	public AbstractEdge(String label, AbstractNode sNode, AbstractNode eNode)
	{
		this.label	= 	label;
		this.sNode	=	sNode;
		this.eNode	=	eNode;
	}
	
	public String getLabel()
	{
		return label;
	}
	
	public AbstractNode getsNode(){
		return sNode;
	}
	
	public AbstractNode geteNode(){
		return eNode;
	}

	
	
}
